import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

class TreeNode {
    public char val;
    public TreeNode left;//左孩子的引用
    public TreeNode right;//右孩子的引用
    public TreeNode(char val) {
        this.val = val;
    }
    public TreeNode() {
        TreeNode treeNode = new TreeNode();
    }
}

public class BinaryTree {
    //public BTNode root;//二叉树的根节点

    /**
     * 这种方式 是穷举的方式创建的
     * 但是 这样写不行 太low了。
     *
     * @return
     */
    public  TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    void preOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    int size(TreeNode root){       //子问题思路      找节点个数
        if(root == null) {
            return 0;
        }
        return size(root.left)+ size(root.right)+1;
    }
    int count = 0;
    int size1(TreeNode root){    //遍历思路
        if(root == null) {
            return count;
        }
        count++;
        size1(root.left);
        size1(root.right);
        return count;
    }
    int getLeafNodeCount(TreeNode root){   //找叶子节点个数，子问题思路
        if(root == null) {
            return 0;
        }else if(root.left == null && root.right == null) {
            return 1;
        } else {
            return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
        }
    }
    int leafcount;
    int getLeafNodeCount1(TreeNode root) {  //找叶子节点个数，遍历思路
        if(root == null) {
            return leafcount;
        }else if(root.left == null && root.right == null) {
            return leafcount++;
        }else {
            getLeafNodeCount1(root.left);
            getLeafNodeCount1(root.right);
        }
        return leafcount;
    }
    int getKLevelSize(TreeNode root,int k) {       //k层节点个数，子问题思路
        if(root == null || k <= 0) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        return getKLevelSize(root.left,k-1)+getKLevelSize(root.right,k-1);
    }
    int getHeight(TreeNode root) {            //最大深度，子问题思路
        if(root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right)) + 1;
    }
    TreeNode find(TreeNode root, char val) {
        if(root == null) {
            return null;
        }
        if(root.val == val) {
            return root;
        }
        TreeNode retnode = find(root.left,val);
        if(retnode != null) {
            return retnode;
        }else {
            return find(root.right,val);
        }
    }
    boolean isCompleteTree(TreeNode root) {   //是否是完全二叉树，利用队列辅助
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode node = queue.peek();
            if(node != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }
    public void levelOrder(TreeNode root) {              //层序遍历
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val+" ");
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    public static int i = 0;
    public static TreeNode createTree1(String str) { //根据先序输入创建二叉树，中序遍历输出
    TreeNode root = null;
    if(str.charAt(i) != '#') {
        root = new TreeNode(str.charAt(i));
        i++;
        root.left = createTree1(str);
        root.right = createTree1(str);
    }else {
        //遇到# 就是空树
        i++;
    }
    return root;
}
    public static void inorder(TreeNode root) {   //中序遍历
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    boolean func(TreeNode root, TreeNode p , Stack<TreeNode> stack) {   //存储路径
        if(root == null || p == null) {
            return false;
        }
        stack.push(root);
        if(root == p) {
            return true;
        }
        if(func(root.left,p,stack)) {
            return true;
        }
        if(func(root.right,p,stack)) {
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  //利用孩子双亲表示法的思想求最近公共祖先
        if (root == null) return null;
        Stack<TreeNode> stack1 = new Stack();
        func(root, p, stack1);
        Stack<TreeNode> stack2 = new Stack();
        func(root, q, stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if (size1 > size2) {
            int size = size1 - size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
            while (!stack1.empty() && !stack2.empty()) {
                if (stack1.peek() == stack2.peek()) {
                    return stack1.peek();
                }
                stack1.pop();
                stack2.pop();
            }
        } else {
            int size = size2 - size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }
            while (!stack1.empty() && !stack2.empty()) {
                if (stack1.peek() == stack2.peek()) {
                    return stack1.peek();
                }
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int inbegin = 0;
        int inend = preorder.length-1;
        return buildTreeChild(preorder,inorder,inbegin,inend);
    }
    public int X = 0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[X]);
        int rootindex = findIndex(inoredr,inbegin,inend,preorder[i]);
        i++;
        root.left = buildTreeChild(preorder,inorder,inbegin,rootindex-1);
        root.right = buildTreeChild(preorder,inorder,rootindex+1,inend);
    }
    public int findIndex(int[] inorder,int inbegin,int inend,int key){
        for(;inbegin<=inend;inbegin++) {
            if(inorder[inbegin] == key) {
                return inbegin;
            }
        }
        return -1;
    }
}

